package leetcode.year2021.month10;

import java.util.ArrayList;
import java.util.List;


/**
 * 22. 括号生成
 */
public class _10_04GenerateParenthesis22 {
  public List<String> generateParenthesis(int n) {
    ArrayList<String> ans = new ArrayList<>();

    StringBuffer stringBuffer = new StringBuffer();

    generateRes(ans,stringBuffer,0,n,n);

    return ans;
  }

  private void generateRes(ArrayList<String> ans, StringBuffer stringBuffer, int index, int left, int right) {
    if (left == 0 && right == 0){
      ans.add(stringBuffer.toString());
    } else if (left == right){
      stringBuffer.append('(');
      generateRes(ans,stringBuffer,index+1,left-1,right);
      stringBuffer.deleteCharAt(index);
    } else if (left < right){
      if (left > 0){
        stringBuffer.append('(');
        generateRes(ans,stringBuffer,index+1,left-1,right);
        stringBuffer.deleteCharAt(index);
      }
      stringBuffer.append(')');
      generateRes(ans,stringBuffer,index+1,left,right-1);
      stringBuffer.deleteCharAt(index);
    }
  }

  /**
   * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
   *
   * 有效括号组合需满足：左括号必须以正确的顺序闭合。
   *
   *  
   *
   * 示例 1：
   *
   * 输入：n = 3
   * 输出：["((()))","(()())","(())()","()(())","()()()"]
   * 示例 2：
   *
   * 输入：n = 1
   * 输出：["()"]
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/generate-parentheses
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */
}
